import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

/**
 * Grafo.java
 * Descripción: Representación de grafo para llevar control sobre los nodos
 * representados en Coordenadas, y de las aristas existentes entre ellos.
 * @since 08/11/2012
 * @version 2.0
 * @author Oscar Castañeda, Carnet 11086 
 *         Diego García, Carnet 11360
 *         Luis Carlos Velásquez, Carnet 11085
 *         Sergio Argueta, Carnet 11029
 */

public class Grafo {
    
    private int[][] matriz; //Matriz de adyacencia del grafo.
    private int[][] mFloyd; //Matriz de distancias para Floyd.
    private int[][] rutasFloyd; //Matriz de rutas para Floyd.
    private int[][] direcciones; //Matriz de direcciones entre nodos.
    private int side; //Largo de un lado del mapa.
    private Integer siguienteNombre; //Siguiente nombre a colocar al próximo nodo.
    private Map<Integer, Coordenada> diccNameToCoord; //Relación nombre - coordenada de nodo.
    private Map<Coordenada, Integer> diccCoordToName; //Relación coordenada de nodo - nombre.
    private ArrayList<Arista> aristas; //Aristas existentes
    
    /**
     * Constructor del grafo.
     * @param side Cantidad de espacios que conforman el lado de una región cuadrada.
     */
    public Grafo(int side){
        this.side = side;
        int sqrSide = side * side;
        //La mayor cantidad de nodos que pueden haber es como espacios existen, que en una región cuadrada de largo size sería size * size.
        matriz = new int[sqrSide][sqrSide];
        //Se inicializa la matriz de adyacencia con todos sus elementos en sqrSide, que sería el número que representa el infinito (Falta de conexión entre nodos),
        //a excepción de los elementos que unen al mismo nodo, a los cuales se les colocará valor cero.
        for (int i=0; i<sqrSide; i++){
            for (int j=0; j<sqrSide; j++){
                if (i==j){
                    matriz[i][j] = 0;
                }else{
                    matriz[i][j] = sqrSide;
                }                
            }
        }        
        direcciones = new int[sqrSide][sqrSide];
        siguienteNombre = new Integer(0);
        diccNameToCoord = new HashMap();
        diccCoordToName = new HashMap();
        aristas = new ArrayList();
    }
        
    /**
     * 
     * @param filaIni
     * @param colIni
     * @param filaDest
     * @param colDest 
     * @pre   filaIni, filaDest, colIni y colDest no pueden ser iguales por pares simultáneamente.
     */
    public void addDirectedEdge (int filaIni, int colIni, int filaDest, int colDest){
        int distancia=-1;
        int direccion=-1;
        //Se crean las coordenadas para los valores dados.
        Coordenada coordInicio = new Coordenada(filaIni, colIni);
        Coordenada coordFinal = new Coordenada(filaDest, colDest);
        //Se revisa si deichas coordenadas existen ya en los diccionarios.
        //  De no existir, se agregan a los diccionarios con el nombre que les toca por el orden en que se agregaron.
        if ((!diccNameToCoord.containsValue(coordInicio))&&(!diccCoordToName.containsKey(coordInicio))){
            diccNameToCoord.put(siguienteNombre, coordInicio);            
            diccCoordToName.put(coordInicio, siguienteNombre);
            siguienteNombre++;
        }
        if ((!diccNameToCoord.containsValue(coordFinal))&&(!diccCoordToName.containsKey(coordFinal))){
            diccNameToCoord.put(siguienteNombre, coordFinal);            
            diccCoordToName.put(coordFinal, siguienteNombre);
            siguienteNombre++;
        }
        //Se obtiene la dirección y magnitud de la arista que une a los nodos indicados.
        if (filaIni==filaDest){
            //Si están sobre la misma fila, la distancia se obtiene de las columnas,
            //y si la columna del destino es mayor que la de inicio, entonces la dirección de la arista es este.
            //De lo contrario es oeste.
            distancia = colDest - colIni;
            if (distancia > 0){
                direccion = 1; //Este
            }else{
                distancia = distancia * -1;
                direccion = 3; //Oeste
            }
        }else{
            if (colIni==colDest){
                //Si están sobre la misma columna, la distancia se obitene de las filas.
                //Si la fila del destino es mayor que la de inicio, entonces la dirección de la arista es sur. En caso contrario, es norte.
                distancia = filaDest - filaIni;
                if (distancia > 0){
                    direccion = 4; //Sur
                }else{
                    distancia = distancia * -1;
                    direccion = 2; //Norte
                }
            }            
        }        
        //Se añade la distancia y dirección de la arista a la matriz de adyacencia y direcciones.
        int mX = diccCoordToName.get(coordInicio).intValue();
        int mY = diccCoordToName.get(coordFinal).intValue();
        matriz[mX][mY] = distancia; //Valores negativos aquí indicarían error.
        direcciones[mX][mY] = direccion; 
        //Se agrega la nueva arista a la lista de aristas, si aun no se encuentra en ella.
        //Se agrega como arista sin dirección, ya que para la aplicación a realizar, se usará un grafo, no un dígrafo.
        Arista theEdge = new Arista(coordInicio, coordFinal);                        
        if(!aristas.contains(theEdge)){
            aristas.add(theEdge);
        }        
    }
    
    /**
     * Añade una arista sin dirección entre los vértices indicados.
     * @param filaIni Fila de uno de los vértices.
     * @param colIni Columna de uno de los vértices.
     * @param filaDest Fila del otro de los vértices.
     * @param colDest  Columna del otro de los vértices.
     */
    public void addEdge(int filaIni, int colIni, int filaDest, int colDest){                
        //Añade la arista en una dirección.
        addDirectedEdge(filaIni, colIni, filaDest, colDest);
        //Añade la arista en la otra dirección.
        addDirectedEdge(filaDest, colDest, filaIni, colIni);                
    }
        
    /**
     * Ejecuta el algoritmo de Floyd sobre el grafo, para hallar los caminos más cortos y las rutas que le corresponden.
     */
    public void floyd(){        
        //Se revisa que ambos diccionarios tengan el mismo tamaño, para verificar brevemente su congruencia.
        if (diccCoordToName.size()==diccNameToCoord.size()){
            //Dicho tamaño es igual al número de nodos en el grafo.
            int cantNodos = diccCoordToName.size();
            //Se inicializa la matriz de Floyd y la que guardará las rutas más cortas.
            mFloyd = new int[cantNodos][cantNodos];
            rutasFloyd = new int[cantNodos][cantNodos];
            //La matriz de Floyd será una copia de la parte realmente utilizada de la matriz de adyacencia
            //y la de direcciones iniciará toda en -1.
            for (int i = 0; i < cantNodos; i++){
                for (int j = 0; j < cantNodos; j++){
                    mFloyd[i][j] = matriz[i][j];
                    rutasFloyd[i][j] = -1;
                }
            }
            //Se realiza el algoritmo de Floyd.
            for (int k = 0; k < cantNodos; k++){
                //Se va considerando un nuevo nodo
                for (int i = 0; i < cantNodos; i++){
                    //Paras las rutas que van desde el nodo i
                    for (int j = 0; j < cantNodos; j++){
                        //hasta el nodo j
                        int caminoNuevo = mFloyd[i][k] + mFloyd[k][j];
                        int caminoViejo = mFloyd[i][j];
                        if (caminoNuevo < caminoViejo){
                            //Si el camino de i a j pasando por k es más corto que el camino
                            //ya conocido de i a j, se cambia dicho camino y se coloca a 
                            //k como vértice intermedio en dicha ruta.
                            mFloyd[i][j] = caminoNuevo;
                            rutasFloyd[i][j] = k;
                        }
                    }
                }
            }
        }else{
            System.out.println("Revisar los diccionarios; son dispares");
        }        
    }
    
    /**
     * Devuelve los nodos del grafo actual.
     * @return ArrayList<Coordenada> con los nodos del grafo existentes, estando cada
     *         uno de ellos colocados en el índice que es igual al número recibido como 
     *         identificador o null si los diccionarios son dispares.
     */
    public ArrayList<Coordenada> getNodos(){
        //Se revisa la congruencia de lso diccionarios.
        if (diccCoordToName.size()==diccNameToCoord.size()){
            int cantNodos = diccCoordToName.size();
            ArrayList<Coordenada> listaNodos = new ArrayList();
            Set<Entry<Integer, Coordenada>> elementosDic = diccNameToCoord.entrySet();
            //Para cada entrada en el diccionario
            for (Entry<Integer, Coordenada> entrada : elementosDic){
                //Se añade al ArrayList listaNodos la coordenada en la posición que es igual al número
                //recibido como identificador.
                listaNodos.add(entrada.getValue());
            }
            return listaNodos;
        }else{
            System.out.println("Revisar los diccionarios; son dispares");
            return null;
        }                        
    }
    
    /**
     * Devuelve las aristas de este grafo.
     * @return ArrayList<Arista> que contiene las aristas del grafo.
     */
    public ArrayList<Arista> getAristas(){
        return aristas;
    }
    
    /**
     * Devuelve la distancia más corta entre dos nodos del grafo dados.
     * @param origen Coordenada con el nodo de partida.
     * @param destino Coordenada del nodo de destino.
     * @return int con la distancia más corta entre los nodos; -1 es error.
     * @pre Llamar a floyd antes.
     */
    public int getShortestPathValue(Coordenada origen, Coordenada destino){
        //Se revisa que las coordenadas ingresadas sean nodos del grafo.
        if (diccCoordToName.containsKey(origen)&& diccCoordToName.containsKey(destino)){
            //Devuelve la distancia más corta entre dichas coordenadas.
            int fila = diccCoordToName.get(origen).intValue();
            int columna = diccCoordToName.get(destino).intValue();
            return mFloyd[fila][columna];
        }else{
            return -1;
        }
    }
    
    /**
     * Devuelve la ruta de los vértices intermedios que llevan de un vértice a otro.
     * @param origen Coordenada del nodo origen.
     * @param destino Coordenada del nodo destino.
     * @return ArrayList<Integer> con los nombres de los vértices intermedios.
     * @pre Debe de ejecutarse floyd().
     * @post Devuelve una lista con las etiquetas de los vértices intermedios entre una ruta y otra.
     */
    public ArrayList<Integer> getShortestPathRoute (Coordenada origen, Coordenada destino){
        ArrayList<Integer> listaAVolver = new ArrayList();
        int fila = diccCoordToName.get(origen).intValue();
        int columna = diccCoordToName.get(destino).intValue();
        verticesRutaMasCorta (fila, columna, listaAVolver);
        listaAVolver.add(0,diccCoordToName.get(origen));
        listaAVolver.add(diccCoordToName.get(destino));
        return listaAVolver;
    }
    
    /**
     * Auxiliar recursivo para hallar los vértices que conforman la ruta más corta.
     * @param fila Número correspondiente al vértice de origen en la matriz de adyacencia.
     * @param columna Número correspondiente al vértice de destino en la matriz de adyacencia.
     * @param resultado Lista que contiene las etiquetas de los vértices intermedios.
     * @return Número correspondiente a un vértice intermedio.
     */
    private int verticesRutaMasCorta (int fila, int columna, ArrayList<Integer> resultado){
        //Se halla el vértice intermedio entre el origen y el destino
        int verticeIntermedio = rutasFloyd[fila][columna];
        //Si existe el vértice intermedio 
        if (verticeIntermedio > -1){
            //Se repite el procedimiento para hallar el vértice intermedio entre el origen y el vértice intermedio.
            verticesRutaMasCorta(fila, verticeIntermedio, resultado);
            //Se añade a la lista de intermedios el vértice intermedio actual
            resultado.add(new Integer(verticeIntermedio));
            //Y se repite el procedimiento para hallar el vértice intermedio entre el intermedio actual y el destino.
            verticesRutaMasCorta(verticeIntermedio, columna, resultado);
        }
        return verticeIntermedio;
    }
    
    /**
     * Devuelve la distancia directa entre dos nodos.
     * @param origen Coordenada del nodo de origen.
     * @param destino Coordenada del notod de destino.
     * @return int con la distancia directa; -1 si hay problema con la cardinalidad de libros.
     * @pre Los nodos deben de ser contiguos.
     */
    public int getDirectRouteValue(Coordenada origen, Coordenada destino){
        if(diccCoordToName.containsKey(origen)&&diccCoordToName.containsKey(destino)){
            int fila = diccCoordToName.get(origen).intValue();
            int columna = diccCoordToName.get(destino).intValue();
            return matriz[fila][columna];
        }else{
            return -1;
        }
    }
    
    /**
     * Devuelve la distancia directa entre dos nodos.
     * @param origen Integer con el hashCode del nodo de origen.
     * @param destino Integer con el hashCode del nodo de destino.
     * @return int con la distancia directa; -1 si hay problema con la cardinalidad de libros.
     * @pre Los nodos deben de ser contiguos.
     */
    public int getDirectRouteValue(Integer origen, Integer destino){
        if(diccNameToCoord.containsKey(origen)&&diccNameToCoord.containsKey(destino)){
            return matriz[origen.intValue()][destino.intValue()];
        }else{
            return -1;
        }
    }
    
    /**
     * Devuelve la dirección entre dos nodos.
     * @param origen Coordenada del nodo de origen.
     * @param destino Coordenada del nodo de destino.
     * @return int con la dirección; -1 si hay problema con la cardinalidad de libros.
     * @pre Los nodos deben de ser contiguos.
     */
    public int getDirectRouteDirection(Coordenada origen, Coordenada destino){
        if(diccCoordToName.containsKey(origen)&&diccCoordToName.containsKey(destino)){
            int fila = diccCoordToName.get(origen).intValue();
            int columna = diccCoordToName.get(destino).intValue();
            return direcciones[fila][columna];
        }else{
            return -1;
        }
    }
    
    /**
     * Devuelve la dirección entre dos nodos.
     * @param origen Integer con el hashCode del nodo de origen.
     * @param destino Integer con el hashCode del nodo de destino.
     * @return int con la dirección; -1 si hay problema con la cardinalidad de libros.
     * @pre Los nodos deben de ser contiguos.
     */
    public int getDirectRouteDirection(Integer origen, Integer destino){
        if(diccNameToCoord.containsKey(origen)&&diccNameToCoord.containsKey(destino)){
            return direcciones[origen.intValue()][destino.intValue()];
        }else{
            return -1;
        }
    }
    
    /**
     * Devuelve el largo del lado del área.
     * @return int con el largo del lado del área.
     */
    public int getSide(){
        return side;
    }
    
}